<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 背包理论基础,语雀记录了笔记：https://www.yuque.com/xiaohangge/gb1rvi/hliixt#I0LoU
        let input = [
            '3 4',
            '1 3 4',
            '15 20 25',
        ]
        let main = (input) => {
            // m物品的种类
            // 1背包的容量
            const [n , bagWeight] = input[0].split(' ').map(Number)
            // 第一行物品的重量
            const weight = input[1].split(' ').map(Number)
            // 第二行物品的价值
            const value = input[2].split(' ').map(Number)

            // 初始化
            // let dp = new Array(n).fill(new Array(bagWeight + 1))
            // 这样初始化，能避免上面初始化导致的变量污染问题
            let dp = new Array(bagWeight + 1).fill(0)

            for (let i = 0; i < n; i++) {
                // 错误遍历顺序
                // for (let j = 1; j <= bagWeight; j++) {
                //     if (j < weight[i]) {
                //         dp[j] = dp[j]
                //     } else {
                //         dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
                //     }
                // }
                // 正确遍历顺序
                for (let j = bagWeight; j >= weight[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
                    console.log(dp, 'dp');
                    debugger
                }
            }
            console.log(dp, 'dp');
            return dp[bagWeight]
        }
        console.log(main(input), 'main(input)');
        
    </script>
</body>

</html>